1. Technical Field
The present invention relates generally to the processing of data and in particular to a multi-processor data processing system. Still more particularly, the present invention relates to a method and apparatus for handling queues in a multi-processor data processing system.
2. Description of the Related Art
Multiprocessor data processing systems contain multiple processors that each can operate on its own data. Typically, these processors operate independently of each other, normally on autonomous tasks or significant portions of large tasks. Multiprocessor systems typically fall into two categories: shared-memory systems and distributed-memory systems. In shared memory systems, the processors communicate by reading and writing data to a shared memory location in a common address space. Additionally, shared memory usually implies a shared bus, but such is not necessarily the case. Within the shared memory, communications between various processors are usually performed through queues. Typically, a large number of queues are commonly used by the data processing system to control usable hardware and software resources within the data processing system, including the queues, which are themselves system resources.
Computer systems with multiple central processing units coupled to a memory system often performed queued operations to organize related blocks of stored data. Queues are data structures used to organize sets of data blocks in memory by means of pointers associated with each data block in a queue. Each queue typically includes a number of elements in which each element is a unit of the queue. Queues may be classified into several general types according to the relative locations of the elements in the queue. Contiguous queues have elements physically located next to each other while linear chained queues are queues with elements physically disbursed anywhere within main or virtual storage. Hierarchical chained queues are queues that speed up queue operation by using hierarchical searching.
The data blocks within queues, whether located physically next to each other or disbursed within main or virtual storage, are associated with each other through linked lists. A xe2x80x9cdoubly linkedxe2x80x9d list has two pointers in each element, pointing to the next and previous elements in the list. In the case of xe2x80x9csingly linkedxe2x80x9d queues, the pointers reference the addresses of successive data blocks in the queue. A singly linked queue is a queue in which each element includes a pointer to its successor in the queue.
Many software systems use queues to store multiple tasks for processing. In some environments, an event or condition encountered during processing requires a context switch to act on the special condition using a different processing algorithm. A context switch is when a processor begins executing in a different software environment, which could include data types, execution priority, interrupt level, or special algorithms. It is possible to have many types of special conditions, each with a separate algorithm for processing. In many software systems, these special events cannot be handled immediately and multiple occurrences must be queued for subsequent processing, requiring support of multiple queues. For execution speed and memory efficiency, however, it is a benefit to utilize as much common software for queue entry handling (e.g., reading/writing queue entries and updating queue pointers) as possible. This use of common software is especially important for environments with limited processing resources, such as embedded processor subsystems.
Therefore, it would be advantageous to have a method and apparatus for multiple queue handling using a common processing algorithm.
The present invention is implemented in a multi-processor data processing system and provides a method for handling a plurality of queues within the data processing system. Each queue is associated with a pointer. A first queue is designated as the current queue along with a first pointer associated with the first queue. This first pointer is designated as a current pointer. Entries are read within the current queue using the current pointer. In response to a condition requiring a change in queues, the current pointer is stored and another pointer is designated or loaded for use as the current pointer. Entries are read with the new current pointer within a queue associated with that pointer.